package daily.year2024.m10;

/**
 * 211.最大正方形
 *
 * @author wjs 2024/10/24
 */
public class d24 {
    //解法一：动态规划
    class Solution1 {
        public int maximalSquare(char[][] matrix) {
            int m = matrix.length, n = matrix[0].length;
            int[][] dp = new int[m][n];
            int res = 0;
            for(int i=0;i < m;i++) {
                for(int j=0;j < n;j++) {
                    if(matrix[i][j] == '1') {
                        dp[i][j] = 1;
                    }
                    if(matrix[i][j] == '0' || i==0 || j==0 || matrix[i-1][j] != '1' || matrix[i][j-1] != '1' || matrix[i-1][j-1] != '1') {
                        res = Math.max(res,dp[i][j]);
                        continue;
                    }
                    dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]);
                    dp[i][j] = Math.min(dp[i][j],dp[i-1][j-1])+1;
                    res = Math.max(res,dp[i][j]);
                }
            }
            return res * res;
        }
    }
}
